package org.raymond.iworks.study.basic.structure.recursion;

/**
 * @author raymond
 * @version V1.0
 * @Description: TODO
 */
public class MazeTest {
    private static int endX = 5;
    private static int endY = 5;
    public static void main(String[] args) {
        int[][] map = buildMap();
        System.out.println("得到的地图:");
        print(map);

        //纳秒, 1秒=1000毫秒,1毫秒=1000微秒,1微秒=1000纳秒
        long start = System.nanoTime();
        findWay2(1,1,map);
        long end = System.nanoTime();
        System.out.printf("耗时%d, 得到的路线:\n", (end-start));
        print(map);
    }

    /**
     * 使用递归回溯来找路
     * @param x 目标x点
     * @param y 目标y点
     * @param map 地图. 从左至右为x轴,最左边的地图起始点下标为0.
     * 从上至下为y轴,最上边的起始点下标为0. 行方向在x轴上,列方向在y轴上.
     * @Description
     * 1,约定:map[x][y] 0-未走过;1-墙,不能走;2-通路,可以走;3-已经走过,但走不通.
     * 2,策略:下->右->上->左,如果走不通,再回溯
     */
    public static boolean findWay(int x, int y, int[][] map){
        // 通路已经找到,返回true
        if(map[endX][endY]==2){
            return true;
        }
        // 还没走过的路,可以走
        if(map[x][y]==0){
            // 按照策略:下->右->上->左 来走
            // 假设当前位置可以走通
            map[x][y]=2;
            // 尝试向下走
            if(findWay(x+1, y, map)){
                return true;
            }
            // 尝试向右走
            if(findWay(x,y+1, map)){
                return true;
            }
            // 尝试向上走
            if(findWay(x-1, y, map)){
                return true;
            }
            // 尝试向左走
            if(findWay(x, y-1, map)){
                return true;
            }
            // 当前位置是死路,走不通
            map[x][y]=3;
            return false;
        }else {
            // 可能的值:1,2,3,都不走了,直接返回false
            return false;
        }
    }

    // 找出最短路径,通过修改策略尝试
    public static boolean findWay2(int x, int y, int[][] map){
        if(map[endX][endY]==2){
            return true;
        }
        if(map[x][y]==0){
            // 按照策略:上>右>下>左
            map[x][y]=2;
            // 尝试向上走
            if(findWay2(x-1, y, map)){
                return true;
            }
            // 尝试向右走
            if(findWay2(x,y+1, map)){
                return true;
            }
            // 尝试向下走
            if(findWay2(x+1, y, map)){
                return true;
            }
            // 尝试向左走
            if(findWay2(x, y-1, map)){
                return true;
            }
            // 当前位置是死路,走不通
            map[x][y]=3;
            return false;
        }else {
            return false;
        }
    }

    public static void print(int[][] map){
        for(int[] row : map){
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    public static int[][] buildMap(){
        // 创建一个二维数组,模拟迷宫
        // 地图, row=8,col=7
        int row = 8;
        int col = 7;
        int[][] map = new int[row][col];
        // 使用1表示墙
        // 上下都置为1,即0行和7行都置为1,逐列设置
        for(int i=0; i<col; i++){
            map[0][i]=1;
            map[row-1][i]=1;
        }
        // 左右都置为1,即0列和6列都置为1,逐行设置
        for(int i=0; i<row; i++){
            map[i][0]=1;
            map[i][col-1]=1;
        }
        // 额外的两堵墙
        map[3][1]=1;
        map[3][2]=1;
        return map;
    }
}
